package recursivecode.trymodel.rangemodel;

import java.util.HashMap;
import java.util.Map;

/**
 * 功能描述:贴纸数
 * 2024/09/13
 *
 * @author ZhangYi
 */
public class StickersCount {
	/**
	 * 数组长度0
	 */
	private final static int ARRAY_LENGTH_0 = 0;

	/**
	 * 单词leghth 26
	 */
	private final static int WORDS_LENGHTH_26 = 26;

	public static void main(String[] args) {
		String[] stickers = new String[]{"aaaa", "bbaa", "ccddd"};

		String target = "abcccccdddddbbbaaaaa";
		int result = getMinStickerCount(stickers, target);
		System.out.println(result);
	}

	/**
	 * 获取最小贴纸计数
	 *
	 * @param stickers 贴纸
	 * @param target   目标字符串
	 * @return int
	 * @author ZhangYi
	 */
	private static int getMinStickerCount(String[] stickers, String target) {
		if (stickers == null || stickers.length == ARRAY_LENGTH_0 || target.length() == ARRAY_LENGTH_0) {
			return 0;
		}
		int N = stickers.length;
		// 获取 贴纸中的词频统计
		int[][] dp = new int[N][WORDS_LENGHTH_26];
		for (int index = 0; index < N; index++) {
			char[] chars = stickers[index].toCharArray();
			if (chars.length == ARRAY_LENGTH_0) {
				continue;
			}
			for (int i = 0; i < chars.length; i++) {
				dp[index][chars[i] - 'a']++;
			}
		}
		Map<String, Integer> map = new HashMap<>();
		map.put("", 0);
		return getMinStickerCount(dp, map, target);
	}

	/**
	 * 获取最小贴纸计数
	 *
	 * @param dp   贴纸的词频统计, 一经生成,不改变
	 * @param map  结果答案的缓存
	 * @param rest 剩余字符串
	 * @return int
	 * @author ZhangYi
	 */
	private static int getMinStickerCount(final int[][] dp, Map<String, Integer> map, String rest) {
		// 如果 map 中 含有当前 剩余字符rest 的处理结果,就直接返回 map 中存储的值即可
		if (map.containsKey(rest)) {
			return map.get(rest);
		}

		char[] chars = rest.toCharArray();
		int[] target = new int[WORDS_LENGHTH_26];
		for (int i = 0; i < chars.length; i++) {
			target[chars[i] - 'a']++;
		}
		int ans = Integer.MAX_VALUE;
		for (int index = 0; index < dp.length; index++) {
			// 如果无法处理 当前的 target中的字符, 就跳过, 开始处理下一个
			if (dp[index][chars[0] - 'a'] == 0) {
				continue;
			}

			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < WORDS_LENGHTH_26; i++) {
				for (int j = 0; j < Math.max(0, target[i] - dp[index][i]); j++) {
					sb.append((char) (i + 'a'));
				}
			}
			// 剩余的字符
			String nextRest = sb.toString();
			int nextAns = getMinStickerCount(dp, map, nextRest);
			if (nextAns != -1) {
				ans = Math.min(ans, nextAns + 1);
			}
		}
		map.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
		return map.get(rest);
	}

}
